package com.bag;

import java.util.*;
import static java.lang.Math.*;

public class dome02 {
    public static void main(String[] args) {
        int n,c;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        c = sc.nextInt();
        int []w = new int[n+1];
        int []v = new int[n+1];
        int []dp = new int[c+1];
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        for(int i=1; i<=n; i++) {
            int num = c/w[i];
            for(int k=1; num>0; k<<=1) {
                if(k>num) k=num;
                num-=k;
                for(int j=c; j>=w[i]*k; j--)
                    dp[j]=max(dp[j], dp[j-w[i]*k]+v[i]*k);
            }
        }

        System.out.println(dp[c]);
    }
}
